package com.base.search.impl.binarysearch;

/**
 * 240. 搜索二维矩阵 II
 *编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年10月25日 19:38
 */
public class SearchMatrix {

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        // 二分查找
        for (int i = 0; i < m; i++) {
            int n = matrix[i].length;
            int left = 0,right = n-1;
            while (left<=right){
                int mid = left + (right - left)/2;
                if (matrix[i][mid] == target){
                    return true;
                }else if(matrix[i][mid]>target){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
        }
        return false;

    }
    // Z字查找法
    // 起始查找点设置为左下角或者右上角
    public boolean searchMatrix1(int[][] matrix,int target){
        // 最左下角元素
        int m = matrix.length,n = 0;

        while (m>0&&n<matrix[0].length){
            if (matrix[m][n]==target){
                return true;
            }else if (matrix[m][n]>target){
                m-=1;
            }else {
                n+=1;
            }
        }
        return false;

    }
}
